%!TEX program = pdflatex
\documentclass[11pt,en]{elegantpaper}

\title{Report for the Project}
\author{Wenchong Huang}

\date{\today}

% cmd for this doc
\usepackage{array}
\usepackage{float}
\usepackage{pgfplots}
\usepackage{tikz}
\usepackage{graphicx}
\usepackage{subfigure}
\newcommand{\ccr}[1]{\makecell{{\color{#1}\rule{1cm}{1cm}}}}

\begin{document}

\maketitle

\section{Introduction}

This project is a simple implemention of piecewise spline interpolation, including linear and cubic. Both are implemented with two different algorithm: ppForm and B-SPline.

For the cubic spline interpolation, five different bondary conditions are supported.

\begin{itemize}
    \item \textit{natural}: $s''(t_1)=s''(t_N)=0$.
    \item \textit{complete}: $s'(t_1)=f'(t_1),\;s'(t_N)=f'(t_N)$.
    \item \textit{second-derivatives-at-end}: $s''(t_1)=f''(t_1),\;s''(t_N)=f''(t_N)$.
    \item \textit{periodic}: $s'(t_1)=s'(t_N),\;s''(t_1)=s''(t_N)$.
    \item \textit{not-a-knot}: $s'''(t_2)$ and $s'''(t_{N-1})$ exist.
\end{itemize}

\textit{natural}, \textit{complete}, \textit{second-derivatives-at-end} and \textit{periodic} are supported in both ppForm and B-Spline. And \textit{not-a-knot} is only supported in ppForm.

For how to use the interpolators, see the document. For how to test, firstly \textbf{run} \verb|make| \textbf{in the sorce code directory}, then read this report to see how to test.

\section{Function Test}

\subsection{Function Fitting}

In this part, we use Runge's function as the example. The results see figure 1-4. Run

\begin{lstlisting}
    ./runge_ppForm > ppForm.txt
    ./runge_BSpline > BSpline.txt
\end{lstlisting}

to get the numerical results in two text files. Copy all the text in \verb|ppForm.txt|, replace line 3-7 of \verb|draw_ppForm_cubic_function.m|. Then run the latter code with \textbf{matlab}. You will get figure 1.

To get figure 2, replace line 21-22 of \verb|test_ppForm_cubic_function.cpp| with

\begin{lstlisting}
    const int n = 11;
    const double xvalue[] = {-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5};
\end{lstlisting}

Then run \verb|make| again, and run \verb|./runge_ppForm > ppForm.txt| again. Do the same work with \textbf{matlab}, you will see figure 2.

To get figure 3 and figure 4, do the similar work to \verb|test_BSpline_cubic_function.cpp| and \verb|draw_| \verb|BSpline_cubic_function.cpp|.

\begin{figure}[htbp]
    \begin{minipage}[t]{0.5\linewidth}
        \centering
        \includegraphics[width=0.9\linewidth]{figure/ppForm_7knots.eps}
        \caption{ppForm, 7 knots.}
        \label{fig:side:a}
    \end{minipage}%
    \begin{minipage}[t]{0.5\linewidth}
        \centering
        \includegraphics[width=0.9\linewidth]{figure/ppForm_11knots.eps}
        \caption{ppForm, 11 knots.}
        \label{fig:side:b}
    \end{minipage}

    \begin{minipage}[t]{0.5\linewidth}
        \centering
        \includegraphics[width=0.9\linewidth]{figure/BSpline_7knots.eps}
        \caption{BSpline, 7 knots.}
        \label{fig:side:c}
    \end{minipage}%
    \begin{minipage}[t]{0.5\linewidth}
        \centering
        \includegraphics[width=0.9\linewidth]{figure/BSpline_11knots.eps}
        \caption{BSpline, 11 knots.}
        \label{fig:side:d}
    \end{minipage}
\end{figure}

Actually, for the same bondary condition, the interpolation results of ppForm and BSpline are the same. There's no significant difference of bondaries \textit{natural}, \textit{complete}, \textit{second-derivatives-at-end} and \textit{periodic}. But the bondary \textit{not-a-knot} performs poor when we only use 7 knots. 

\subsection{Curve Generating}

In this part, we connect some discrete points in 2D plane with a cubic spline curve. Run

\begin{lstlisting}
    ./curve > curve.txt
\end{lstlisting}

to get the numerical in a text file. Copy the text in \verb|curve.txt| and replace line 1-9 of \verb|draw_random_curve.m| with it. Run the latter code with \textbf{matlab} then you will see the result.

The result sees figure 5.

\begin{figure}[htbp]
    \centering
    \begin{minipage}[t]{0.5\linewidth}
        \centering
        \includegraphics[width=0.7\linewidth]{figure/curve_random.eps}
        \caption{Generated cueve with discrete points.}
        \label{fig:side:a}
    \end{minipage}
\end{figure}

Two bondaries are supported. To generate closed curve, we suggest using bondary \textit{periodic}. It gives a more smooth curve than bondary \textit{natural}.

\subsection{Open Curve Fitting}

In this part, we use Helix curve $\rho=\theta$ as the example. Run

\begin{lstlisting}
    ./helix natural > natural.txt
    ./helix complete > complete.txt
    ./helix second-derivatives-at-end > sdae.txt
\end{lstlisting}

to get the numerical in text files. Copy the text and replace line 4-7 of \verb|draw_curve_helix.m| with it. Run the latter code with \textbf{matlab} then you will see the result. Use the different text to get the figure of different bondaries.

The results see figure 6-8.

\begin{figure}[htbp]
    \centering
    \begin{minipage}[t]{0.32\linewidth}
        \centering
        \includegraphics[width=0.9\linewidth]{figure/curve_helix_complete.eps}
        \caption{\textit{complete}}
        \label{fig:side:a}
    \end{minipage}%
    \begin{minipage}[t]{0.32\linewidth}
        \centering
        \includegraphics[width=0.9\linewidth]{figure/curve_helix_natural.eps}
        \caption{\textit{natural}}
        \label{fig:side:b}
    \end{minipage}
    \begin{minipage}[t]{0.35\linewidth}
        \centering
        \includegraphics[width=0.9\linewidth]{figure/curve_helix_second-derivatives-at-end.eps}
        \caption{\textit{second-derivatives-at-end}}
        \label{fig:side:c}
    \end{minipage}%
\end{figure}

The bondaries \textit{complete} and \textit{second-derivatives-at-end} performs better.

\subsection{Closed Curve Fitting}

In this part we use Cardioid curve as the example. Run

\begin{lstlisting}
    ./cardioid natural > natural.txt
    ./cardioid complete > complete.txt
    ./cardioid second-derivatives-at-end > sdae.txt
    ./cardioid periodic > periodic.txt
\end{lstlisting}

to get the numerical in text files. Copy the text and replace line 4-7 of \verb|draw_curve_cardioid.m| with it. Run the latter code with \textbf{matlab} then you will see the result. Use the different text to get the figure of different bondaries.

The results see figure 9-12.

\begin{figure}[htbp]
    \centering
    \begin{minipage}[t]{0.4\linewidth}
        \centering
        \includegraphics[width=0.9\linewidth]{figure/curve_cardioid_complete.eps}
        \caption{\textit{complete}}
        \label{fig:side:a}
    \end{minipage}%
    \begin{minipage}[t]{0.4\linewidth}
        \centering
        \includegraphics[width=0.9\linewidth]{figure/curve_cardioid_natural.eps}
        \caption{\textit{natural}}
        \label{fig:side:b}
    \end{minipage}
    \begin{minipage}[t]{0.4\linewidth}
        \centering
        \includegraphics[width=0.9\linewidth]{figure/curve_cardioid_second-derivatives-at-end.eps}
        \caption{\textit{second-derivatives-at-end}}
        \label{fig:side:c}
    \end{minipage}%
    \begin{minipage}[t]{0.4\linewidth}
        \centering
        \includegraphics[width=0.9\linewidth]{figure/curve_cardioid_periodic.eps}
        \caption{\textit{periodic}}
        \label{fig:side:c}
    \end{minipage}%
\end{figure}

The bondary \textit{natural} performed worse than others. The local behavior at the end sees figure 13-16.

\begin{figure}[htbp]
    \centering
    \begin{minipage}[t]{0.24\linewidth}
        \centering
        \includegraphics[width=0.9\linewidth]{figure/curve_cardioid_complete_local.eps}
        \caption{\textit{complete}}
        \label{fig:side:a}
    \end{minipage}%
    \begin{minipage}[t]{0.24\linewidth}
        \centering
        \includegraphics[width=0.9\linewidth]{figure/curve_cardioid_natural_local.eps}
        \caption{\textit{natural}}
        \label{fig:side:b}
    \end{minipage}
    \begin{minipage}[t]{0.24\linewidth}
        \centering
        \includegraphics[width=0.9\linewidth]{figure/curve_cardioid_second-derivatives-at-end_local.eps}
        \caption{\textit{second-derivatives-at-end}}
        \label{fig:side:c}
    \end{minipage}%
    \begin{minipage}[t]{0.24\linewidth}
        \centering
        \includegraphics[width=0.9\linewidth]{figure/curve_cardioid_periodic_local.eps}
        \caption{\textit{periodic}}
        \label{fig:side:c}
    \end{minipage}%
\end{figure}

The end of periodic curve is smooth while others are sharp.

\section{Programming Assignments}

\subsection{Assignment A}

Run

\begin{lstlisting}
    ./A N > A.txt
\end{lstlisting}

to get the numerical result, where $N$ are the number of knots. Copy the text and replace line 3-4 of \verb|draw_A.m|, then run the latter code with \textbf{matlab}. You will see the figures as following.

\begin{figure}[htbp]
    \centering
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/assA_N=6.eps}
        \caption{$N=6$}
        \label{fig:side:a}
    \end{minipage}%
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/assA_N=11.eps}
        \caption{$N=11$}
        \label{fig:side:b}
    \end{minipage}
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/assA_N=21.eps}
        \caption{$N=21$}
        \label{fig:side:c}
    \end{minipage}%
\end{figure}

The max error sees the following table.

\begin{table}[htbp]
    \centering
    \begin{tabular}{c|cccccc}
    \textbf{$N$} & 6        & 11        & 21         & 41          & 81        & 501         \\ \hline
    max error    & 0.421696 & 0.0205293 & 0.00316894 & 0.000275356 & 1.609e-05 & 1.64707e-06
    \end{tabular}
\end{table}

We can plot the logarithm of max error. And compare it with logarithm of $N^{-2}$ and $N^{-3}$. As the following figure shows.

\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{figure/maxerr_log.eps}
    \caption{logarithm of max error and $N^{-2}$, $N^{-3}$.}
\end{figure}

So the convergence rate may appoximate to be of order two.

\subsection{Assignment C}

Run

\begin{lstlisting}
    ./C > runge.txt
\end{lstlisting}

to get the numerical result in a text file. Copy the text and replace line 3-4 of \verb|draw_C.m|, then run the latter code with \textbf{matlab}. You will see the figure as following.

\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.4\textwidth]{figure/assC.eps}
    \caption{The interpolating result of quadratic B-spline and cubic(complete) B-spline.}
\end{figure}

\subsection{Assignment D}

Run \verb|./D| directly to see the result, as the following table shows.

\begin{table}[htbp]
    \centering
    \begin{tabular}{c|ccccccc}
    \textbf{point}            & -3.5        & -3         & -0.5      & 0        & 0.5         & 3          & 3.5         \\ \hline
    $E_{S}(\text{quadratic})$ & 0           & 0.00141838 & 0         & 0.120238 & 1.11022e-16 & 0.00141838 & 0           \\
    $E_{S}(\text{cubic})$     & 0.000505852 & 0          & 0.0205266 & 0        & 0.0205266   & 0          & 0.000505852
    \end{tabular}
\end{table}

The points $-3.5, -0.5, 0.5, 3.5$ are knots of quadratic B-spline, hence the error are close to machine precision. So does $-3,0,3$ to cubic B-spline. We could see that the cubic B-spline is more accurate.

\subsection{Assignment E}

We use the following parametrization (not unit-speed).
\begin{align*}
    \gamma(\theta) = \left(\sqrt{3} \sin\theta,\;\; \frac{2}{3}\left(\sqrt{3}\sin\theta + \left(\sqrt{3}|\cos \theta|\right)^\frac{1}{2}\right) \right)
\end{align*}
where $\theta\in[-\frac{\pi}{2},\frac{3\pi}{2}]$. 

We can numerically compute the length of curve between $\gamma(\theta_l)$ and $\gamma(\theta_r)$ with \textbf{divide-and-conquer strategy}. So we can use \textbf{bisection method} to find $\theta_0,\cdots,\theta_N$, such that the length of curve between $\gamma(\theta_i)$ and $\gamma(\theta_{i+1})$ are equal for $i=0,...,N-1$.

Run
\begin{lstlisting}
    ./E natural 10 > E.txt
\end{lstlisting}
to get the numerical result of natural cubic B-Spline with $10$ vertexes. Also replace $10$ with $40, 160$ and replace \verb|natural| with \verb|periodic| to get other results. Copy the text to \verb|draw_E.m| to generate the figures as following.

\begin{figure}[htbp]
    \centering
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/assE_10knots.eps}
        \caption{natural, 10 knots.}
        \label{fig:side:a}
    \end{minipage}%
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/assE_40knots.eps}
        \caption{natural 40 knots.}
        \label{fig:side:b}
    \end{minipage}
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/assE_160knots.eps}
        \caption{natural, 160 knots.}
        \label{fig:side:c}
    \end{minipage}%
\end{figure}

\begin{figure}[htbp]
    \centering
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/assE_10knots_periodic.eps}
        \caption{periodic, 10 knots.}
        \label{fig:side:a}
    \end{minipage}%
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/assE_40knots_periodic.eps}
        \caption{periodic 40 knots.}
        \label{fig:side:b}
    \end{minipage}
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/assE_160knots_periodic.eps}
        \caption{periodic, 160 knots.}
        \label{fig:side:c}
    \end{minipage}%
\end{figure}

As we can see, fit the shape with 40 knots is enough.

Morever, notice the end of the shape is sharp. But boundary \textit{periodic} always gives smooth end. So use boundary \textit{natural} is more appropriate.

\end{document}
